package com.kizuki.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 */
public class 无重复字符的最长子串 {

    class Solution {

        // start不动，end向后移动
        // 当end遇到重复字符，start应该放在上一个重复字符的位置的后一位，同时记录最长的长度
        public int lengthOfLongestSubstring(String s) {
            if (s.length() == 0) {
                return 0;
            }
            int ans = 0, start = 0;
            Map<Character, Integer> map = new HashMap<>();
            for (int end = 0; end < s.length(); end++) {
                if (map.containsKey(s.charAt(end))) {
                    start = Math.max(start, map.get(s.charAt(end)) + 1);
                }
                map.put(s.charAt(end), end);
                ans = Math.max(ans, end - start + 1);
            }
            return ans;
        }
    }

}
